/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
  if (height == null || height.length <= 2) return 0;

  const lefts = [0];
  for (let i = 1; i < height.length; i++) {
    const last = lefts[lefts.length - 1];
    if (height[i] >= height[last]) {
      lefts.push(i);
    }
  }

  let result = 0;
  if (lefts.length > 1) {
    for (let i = 1; i < lefts.length; i++) {
      const prevIndex = lefts[i - 1];
      const currIndex = lefts[i];
      if (prevIndex + 1 < currIndex) {
        // 说明两个指标间有空隙
        const prevHeight = height[prevIndex];
        for (let j = prevIndex + 1; j < currIndex; j++) {
          result += prevHeight - height[j];
        }
      }
    }
  }

  const maxHeightIndex = lefts[lefts.length - 1];

  if (height.length - 1 > maxHeightIndex) {
    // 说明最后一个不是最高的柱子，逆序再来一遍
    const rights = [height.length - 1];
    for (let i = height.length - 2; i >= 0; i--) {
      const last = rights[rights.length - 1];
      if (last == maxHeightIndex) break;
      if (height[i] >= height[last]) {
        rights.push(i);
      }
    }

    if (rights.length > 1) {
      for (let i = 1; i < rights.length; i++) {
        const prevIndex = rights[i - 1];
        const currIndex = rights[i];
        if (prevIndex > currIndex + 1) {
          // 说明两个指标间有空隙
          const prevHeight = height[prevIndex];
          for (let j = currIndex + 1; j < prevIndex; j++) {
            result += prevHeight - height[j];
          }
        }
      }
    }
  }

  return result;
};

console.log(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]));
